//Cracking the coding interview (5th), 3_2
//How would you design a stack which, in addition to push and pop,
//also has a function min which returns the minimum element?
//Push, pop and min should all operate in O(1)time
//author: Fan Yang

#include<stdio.h>
#include<stdlib.h>

typedef struct List
{
	int data;
	struct List * next;
	int min;//local min
}StackNode;

StackNode * Top;

int Push(StackNode * stack,int e)
{
	StackNode * p;
	p=(StackNode *)malloc(sizeof(StackNode));
	p->data=e;
	if(Top->min>e)
	{
		p->min=e;
	}
	else
	{
		p->min=Top->min;
	}
	p->next=NULL;
	Top->next=p;
	Top=p;
	return 1;
}

int Pop(StackNode * stack)
{
	int data=Top->data;
	StackNode *p = stack;
	while(p->next!=Top)
	{
		p=p->next;
	}
	Top=p;
	Top->next=NULL;
	return data;
}

int GetMin()
{
	return Top->min;
}

void main()
{
	StackNode * head=NULL;
	int Data[10],status;
	for(int i=0;i<10;i++)
	{
		printf("Input the %d number: ",i);
		scanf("%d", &Data[i]);
	}
	head=(StackNode *)malloc(sizeof(StackNode));
	head->data=Data[0];
	head->min=Data[0];
	head->next=NULL;
	Top=head;
	for(int i=1;i<10;i++)
	{
		status=Push(head,Data[i]);
	}
	for(int i=1;i<10;i++)
	{
		int elem,min;
		elem=Pop(head);
		min=GetMin();
		printf("The top element of the stack is %d.\n",elem);
		printf("The min element of the stack is %d.\n",min);
	}
}
